/* 
  1 <= k
  思路：
    可以使用快速排序分区的思想进行解题，在快排中，当进行一次partition之后，
  返回一个p，那么p就已经是排好序的了，此时
  如果p = k - 1，说明就已经找到了
  如果p < k - 1，说明就要去右边继续找
  如果p > k - 1，说明就要去左边继续找

*/
var swap = (arr, i, j) => {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
};

var partition = (arr, l, r) => {
  // 二路快排 这里需要加一是因为初始的时候，还没有处理i,j上的元素
  // 保证：arr[j+1, i - 1] <= arr[l] arr[j + 1, r] >= arr[l]
  let tempPartition = Math.floor(Math.random() * (r - l + 1)) + l;
  swap(arr, l, tempPartition);
  let i = l + 1;
  let j = r;
  while (true) {
    while (i <= j && arr[i] > arr[l]) {
      // 寻找第一个大于arr[l]的值，并停在这个位置
      i++;
    }
    while (j >= i && arr[j] < arr[l]) {
      // 寻找第一个大于arr[l]的值，并停在这个位置
      j--;
    }
    if (i >= j) {
      // 说明已经比较完了
      break;
    }
    swap(arr, i, j);
    i++;
    j--;
  }
  // 此时需要和l交换位置
  swap(arr, l, j);
  return j;
};
var _search = (arr, l, r, k) => {
  var p = partition(arr, l, r);
  if (p > k - 1) {
    return _search(arr, l, p - 1, k);
  }

  if (p < k - 1) {
    return _search(arr, p + 1, r, k);
  }
  return arr[p];
};

var findKthLargest = function (nums, k) {
  const num = _search(nums, 0, nums.length - 1, k);
  return num;
};

var arr = [3, 2, 3, 1, 2, 4, 5, 5, 6];
console.log(findKthLargest(arr, 4));
